package dynamicProgramming.bagQuestion;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Class494 {

    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
//        int size=(sum+target)/2;
//TODO:2024/1/27  别忘了加上这个限制条件
        if ( target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[][] dp=new int[nums.length+1][size+1];


        //TODO:2024/1/27  一直不对 是因为初始化有问题
        //TODO:2024/1/27 初始化列的值
        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);
        }
//
//        for (int i = 0; i <=nums.length; i++) {
//            dp[i][0]=1;
//        }


        //TODO:2024/1/27  第一版本
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <=size; j++) {
                //TODO:2024/1/27  这里少了这样的一句
                dp[i][j]=dp[i-1][j];
                if (j>=nums[i-1]){
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
                }
            }
        }


//TODO:2024/1/27 第二版本
//        for (int i = 1; i <= nums.length; i++) {
//            for (int j = 0; j <=size; j++) {
//                //TODO:2024/1/27  这里少了这样的一句
//                if (dp[i][j]<nums[i-1]){
//                    dp[i][j]=dp[i-1][j];
//                }
//                else {
//                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
//                }
//            }
//        }

        return  dp[nums.length][size];
    }



    public int findTargetSumWays1(int[] nums, int target) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (target<0&&sum<-target){
            return 0;
        }
        if ((target+sum)%2!=0)  return 0;
        int size=(target+sum)/2;
        if (size<0) size=-size;

        //  CKG TODO 2023/6/1: 定义dp数组
        int[] dp=new int[size+1];
        dp[0]=1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >=nums[i] ; j--) {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[size];
    }

    LinkedList<Integer> path;
    List<List<Integer>>  ans;
    public int findTargetSumWays2(int[] nums, int target) {

        path=new LinkedList<>();
        ans=new ArrayList<>();
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (target<0&&sum<-target){
            return 0;
        }
        if ((target+sum)%2!=0)  return 0;
        int size=(target+sum)/2;
        if (size<0) size=-size;
        backTracking(nums,size,0,0);
        return  ans.size();
    }

    public   void  backTracking(int[] nums,int target,int start,int sum){
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (start>=nums.length){
            return;
        }
        for (int i = start; i < nums.length; i++) {
            sum+=nums[i];
            path.add(nums[i] );
            backTracking(nums, target, i+1, sum);
            sum-=nums[i];
            path.removeLast();
        }



    }







        public static void main(String[] args) {
        Class494 class494 = new Class494();
        int[] arr={0,0,0,0,0,0,0,0,1};
        System.out.println(class494.findTargetSumWays(arr, 1));
    }
}
